package org.myy.learn.hot.动态规划;

import lombok.extern.slf4j.Slf4j;

@Slf4j
public class 最长递增子序列 {
    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n < 2){return n;}
        int[] dp = new int[n];
        dp[0] = 1;
        int lengthOfLIS = 0;
        for (int i=1; i<n; i++){
            dp[i] = 1;
            for (int j=0; j<i; j++){//未要求连续子序列
                if (nums[i] > nums[j]){  //是递增，不是非递减
                    dp[i] = Math.max(dp[j]+1, dp[i]);
                }
            }
            lengthOfLIS = Math.max(lengthOfLIS, dp[i]); //尾节点可能小于倒数第二节点
        }
        return lengthOfLIS;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{10,9,2,5,3,7,101,18};
        int lengthOfLIS = lengthOfLIS(nums);
        log.info("执行结束，最长递增子序列={}", lengthOfLIS);
    }

}
